In a computer system which allows several processes to co-exist (e.g. a multi-tasking operating system or multi-processor system) a means to synchronize the processes is needed. The semaphore mechanism is a common approach to solving this need. Although the term semaphore has been used to describe several synchronization mechanisms we will use it only to mean the algorithms devised by E. W. Dijkstra.
The essence of Dijkstra's semaphores is a data structure and algorithm which control the use of resources. In computers semaphores are used to protect data structures in the computer's memory, to arbitrate the use of devices and to synchronize processes with external events.
Previous computer systems have implemented semaphores using a software or microcode algorithm. In multiprocessor systems the performance of the semaphore mechanism determines the degree of parallelism which can be achieved and thus the system performance.
Each semaphore includes a counter which describes the quantity of particular resources which are available, and if no resources are available it may include a list of processes waiting for a resource to be made available.
Dijkstra defined two operations which act on semaphores:
P(sema): Allocate a resource to the process. Blocking the process if necessary until a resource is available. While a process is blocked the processor may be running another process. PA1 V(sema): Return a resource allocated using P to the pool of resources and if a process is waiting for the resource allocate the resource to that process that make it runable.
The P operation decrements the counter and then decides if it needs to block the process. The V operation increments the counter and decides if there is a process waiting to run. Semaphores have been implemented on existing systems using software to implement the algorithms. These algorithms are difficult to implement in software since the semaphore data structure itself is a resource which needs to be protected.
The normal hardware support commonly used to provide synchronization of semaphores is an indivisible memory read/modify/write operation. Software can build on this by repeatedly doing an indivisible test and set operation on a lock bit in memory until it finds that the bit was previously cleared. This is called a spin loop because contention for the lock bit is resolved by the processor spinning in a tight loop waiting for the resource to become available.
If a spin lock is used to protect the semaphore data structure, the semaphore operations are just the increment or decrement of the counter and manipulation of the list of processes waiting for the semaphore.
Semaphores implemented in software can degrade the performance of a multiprocessor computer system in several ways: Many semaphore operations per second can result in a high degree of contention for the common bus and therefore the semaphore operations can take a significant amount of time compared to the code which they protect. The indivisible bus operations can seriously affect the through-put of the system bus. The duration of the semaphore operation effects the contention for the semaphore itself.